package com.LeeCode;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

/**
 * 二叉树灯饰
 */

public class CodeLCP064 {
    public static void main(String[] args) {

    }

    class CacheKey {
        TreeNode node;
        boolean switch2, switch3;

        public CacheKey(TreeNode node, boolean switch2, boolean switch3) {
            this.node = node;
            this.switch2 = switch2;
            this.switch3 = switch3;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof CacheKey)) return false;
            CacheKey that = (CacheKey) o;
            return switch2 == that.switch2 &&
                    switch3 == that.switch3 &&
                    node == that.node;
        }

        @Override
        public int hashCode() {
            return Objects.hash(node, switch2, switch3);
        }
    }

    private Map<CacheKey, Integer> memo = new HashMap<>();

    public int closeLampInTree(TreeNode root) {
        return dfs(root, false, false);
    }

    private int dfs(TreeNode node, boolean switch2, boolean switch3) {
        if (node == null) {
            return 0;
        }

        CacheKey key = new CacheKey(node, switch2, switch3);
        if (memo.containsKey(key)) {
            return memo.get(key);
        }

        int res;

        // 判断当前节点是否亮着
        if ((node.val == 1) == (switch2 == switch3)) {
            // 当前节点亮着，需要关掉它
            int res1 = dfs(node.left, switch2, false) + dfs(node.right, switch2, false) + 1;
            int res2 = dfs(node.left, !switch2, false) + dfs(node.right, !switch2, false) + 1;
            int res3 = dfs(node.left, switch2, true) + dfs(node.right, switch2, true) + 1;
            int r123 = dfs(node.left, !switch2, true) + dfs(node.right, !switch2, true) + 3;
            res = min(res1, res2, res3, r123);
        } else {
            // 当前节点已经熄灭
            int res0 = dfs(node.left, switch2, false) + dfs(node.right, switch2, false);
            int res12 = dfs(node.left, !switch2, false) + dfs(node.right, !switch2, false) + 2;
            int res13 = dfs(node.left, switch2, true) + dfs(node.right, switch2, true) + 2;
            int res23 = dfs(node.left, !switch2, true) + dfs(node.right, !switch2, true) + 2;
            res = min(res0, res12, res13, res23);
        }

        memo.put(key, res);
        return res;
    }

    private int min(int... nums) {
        int minVal = Integer.MAX_VALUE;
        for (int num : nums) {
            minVal = Math.min(minVal, num);
        }
        return minVal;
    }
}
